package ds.tree;

public class MaxWidthUsingPreOrderTraversal {
	
	private int[] count =null ;
	
	private int height(TreeNode node) {
		if(node == null){
			return 0;
		}
		return 1 + Math.max(height(node.left), height(node.right));
	}
	
	private int getMaxWidth(TreeNode node){
		int height = height(node);
		count = new int[height];
		traversal(node,0);
		int max = 0;
		for (int i = 0; i < count.length; i++) {
			if(max < count[i]){
				max=count[i];
			}
		}
		return max;
	}
	
	private void traversal(TreeNode node,int level){
		if(node == null){
			return;
		}
		count[level] ++;
		traversal(node.left, level+1);
		traversal(node.right,level+1);
	}
	private static TreeNode tree(){
		TreeNode A = new TreeNode(1);
		TreeNode B = new TreeNode(2);
		TreeNode C = new TreeNode(3);
		TreeNode D = new TreeNode(4);
		TreeNode E = new TreeNode(5);
		
		A.left = B;
		A.right = C;
		B.left = D;
		B.right = E;
		
		return A;
	}
	private static class TreeNode{
		int value;
		TreeNode left = null;
		TreeNode right = null;
		
		TreeNode(int val){
			this.value = val;
		}
		
		public String toString(){
			return String.valueOf(value);
		}
	}
	
	public static void main(String[] args) {
		MaxWidthUsingPreOrderTraversal maxWidth = new MaxWidthUsingPreOrderTraversal();
		System.out.println(" Max Width = " + maxWidth.getMaxWidth(tree()));
	}
}
